//定义邻接矩阵
let arr2 = [
	[0, 1, 5, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity],
	[1, 0, 3, 7, 5, Infinity, Infinity, Infinity, Infinity],
	[5, 3, 0, Infinity, 1, 7, Infinity, Infinity, Infinity],
	[Infinity, 7, Infinity, 0, 2, Infinity, 3, Infinity, Infinity],
	[Infinity, 5, 1, 2, 0, 3, 6, 9, Infinity],
	[Infinity, Infinity, 7, Infinity, 3, 0, Infinity, 5, Infinity],
	[Infinity, Infinity, Infinity, 3, 6, Infinity, 0, 2, 7],
	[Infinity, Infinity, Infinity, Infinity, 9, 5, 2, 0, 4],
	[Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, 7, 4, 0],
]

let vs = 9, //定义顶点数
	edgesNs = 15; //定义边数

// 定义图结构  
function MGraph() {
	this.vexs = []; //顶点表
	this.arc = []; // 邻接矩阵，可看作边表
	this.vs = null; //图中当前的顶点数
	this.edgesNs = null; //图中当前的边数
}
let G = new MGraph(); //创建图使用

//创建图
function createMGraph() {
	G.vs = vs; //设置顶点数
	G.edgesNs = edgesNs; //设置边数

	//录入顶点信息
	for (let i = 0; i < G.vs; i++) {
			G.vexs[i] = 'V' + i; //scanf('%s'); //ascii码转字符 //String.fromCharCode(i + 65);
	}
	console.log(G.vexs) //打印顶点

	//邻接矩阵初始化
	for (let i = 0; i < G.vs; i++) {
			G.arc[i] = [];
			for (var j = 0; j < G.vs; j++) {
					G.arc[i][j] = arr2[i][j]; //INFINITY; 
			}
	}
	console.log(G.arc); //打印邻接矩阵
}




function Dijkstra() {
	let pathMatirx = [] // 用于存储最短路径下标的数组，下标为各个顶点，值为下标顶点的前驱顶点
  let shortPathTable = [] //用于存储到各点最短路径的权值和
	let k, min;
	let final = [];
	for (let v = 0; v < G.vs; v++) {
			final[v] = 0;
			shortPathTable[v] = G.arc[0][v];
			pathMatirx[v] = 0;
	}
	shortPathTable[0] = 0;
	final[0] = 1;

	for (let v = 1; v < G.vs; v++) { //初始化数据
			min = Infinity;
			for (let w = 0; w < G.vs; w++) { //寻找离V0最近的顶点
					if (!final[w] && shortPathTable[w] < min) {
							k = w;
							min = shortPathTable[w]; //w 顶点离V0顶点更近
					}
			}
			final[k] = 1; //将目前找到的最近的顶点置位1
			for (let i = 0; i < G.vs; i++) { //修正当前最短路径及距离
					if (!final[i] && (min + G.arc[k][i] < shortPathTable[i])) { //说明找到了更短的路径，修改Pathmatirx[w]和ShortPathTable[w]
							shortPathTable[i] = min + G.arc[k][i];
							pathMatirx[i] = k;
					}
			}
	}
	return { pathMatirx, shortPathTable }
}

function PrintVn(Vn) {
	var { pathMatirx, shortPathTable } = Dijkstra();
	console.log({ pathMatirx, shortPathTable })
	console.log(G)
	//打印V0-Vn最短路径
	// console.log("%s-%s 最小权值和: %d", G.vexs[0], G.vexs[Vn], shortPathTable[Vn]);
	//打印最短路线
	let temp = Vn,
			str = '';
	while (temp != 0) {
			str = '->' + G.vexs[temp] + str
			temp = pathMatirx[temp]
	}
	str = 'V0' + str;
	console.log('最短路线：'+str);
}

createMGraph();

PrintVn(8);